The invention relates to the field of data communication networks. More particularly, the present invention relates to methods and apparatus for scheduling data packets being sent within a data communication network.
In a network that serves multiple user entities for various different purposes, it is important that the resources of the network are allocated appropriately. For example, it may be desired to dynamically allocate network resources between important or time-critical communications and those that are of lower importance or are less time-critical. This is to ensure that all communications reach their destinations when needed (or least to ensure that only low importance communications are subject to significant delays). For example, certain communications may be intolerant to delays, such as voice or video communications. In addition, certain network users may desire higher levels of network availability than others. Conversely, other users or other types of communications, such as batch file transfers, may be more tolerant of communication delays.
In network equipment, such as switches or routers, data packets are typically received and buffered prior to retransmission. The equipment then forwards the data packets to their appropriate destinations and may also perform other functions. For example, each piece of network equipment may allocate network resources to the various data communications it receives by appropriately scheduling its buffered packets before forwarding them. As computer networks evolve, there is an ever-increasing need to provide more bandwidth, lower latency, decreased costs and increased flexibility. Accordingly, there is a need to provide techniques for scheduling the retransmission of data packets that respond to these needs.
A conventional technique for scheduling retransmission of data packets involves the use of a heap data structure. Packets awaiting retransmission are placed in the heap and arranged in accordance with their priorities prior to retransmission. Accordingly, what is needed is a technique for filling and emptying the heap quickly and efficiently. What is further needed is a technique for quickly and efficiently arranging the heap.
Aspects of the invention are variously directed to these ends.
The present invention is directed toward data packet transmission scheduling. Scheduling values, such as priority or other scheduling criteria assigned to data packets, are placed in a scheduling heap data structure. Packets percolate up through the heap by comparing their assigned values in pairs. Operations in the heap may be pipelined so as to provide for high-speed sorting. Thus, a few relatively simple operations can be performed repeatedly to quickly percolate packets up through the heap. Another aspect of the invention provides for fast traversal of the scheduling heap data structure. The hierarchical heap may include a highest level having a single position and each succeeding lower level having twice the number of positions as the preceding level. A binary number may represent each position in the heap. To traverse the heap, the relative movements necessary to move from one position to another may be determined from the binary number. This is useful to quickly and efficiently traverse the heap.